package 代码随想录.数组.二分查找;

import com.sun.javafx.image.BytePixelSetter;

import javax.sound.midi.MidiChannel;

/**35. 搜索插入位置
 * link:https://leetcode-cn.com/problems/search-insert-position/
 * @author ChenweiLin
 * @create 2021-11-28 18:47
 */
public class searchInsertPosition {
    public static void main(String[] args) {
        int[] nums = new int[]{1,3,5,6};
        int[] targets = new int[]{5,2,7,0};
        for (int target : targets) {
            System.out.println(searchInsert(nums, target));
        }

    }
    public static int searchInsert(int[] nums, int target) {
        //特殊情况
        if(target <= nums[0])
            return 0;
        if(target > nums[nums.length-1])
            return nums.length;

        int left = 0,right = nums.length-1;
        int mid = left + ((right-left)/2);
        while (left <= right){
            mid = left + ((right-left)/2);
            if(target == nums[mid]){
                return mid;
            }else if (target > nums[mid]){
                left = mid+1;
            }else if (target < nums[mid]){
                right = mid -1;
            }
        }

        return right+1;//todo 返回位置
    }
}
